1. Field of the Invention
The present invention relates to a cryptographic technology used as an information security technology. The present invention particularly relates to a technology of distributing a key, in secrecy.
2. Description of Related Art
Conventionally, the public-key cryptosystem has been used for transmitting information from a transmission apparatus to a reception apparatus in secrecy.
In the public-key cryptosystem, a transmission apparatus encrypts a communication content using the public key of a reception apparatus, and sends the encrypted communication content to the reception apparatus. The reception apparatus receives the encrypted communication content, and decrypts the encrypted communication content using a secret key, thereby obtaining the original communication content (e.g. refer to the non-patent reference 1).
In the year of 1996, the NTRU cryptosystem was proposed, as a public-key cryptosystem for high-speed processing (e.g. refer to the non-patent reference 2). The NTRU cryptosystem performs encryption/decryption using a polynomial operation that enables high-speed computation. The NTRU cryptosystem enables higher-speed processing using software, compared to the conventional public-key cryptosystems such as the RSA cryptosystem and the elliptic curve cryptosystem, the RSA cryptosystem performing exponentiation, and the elliptic curve cryptosystem performing scalar multiplication on a point of an elliptic curve.
In this NTRU cryptosystem, a decrypted text is generated by the processes in which the plaintext is encrypted using the public key to generate a cipher text, and then this cipher text is decrypted using the secret key. However, the mentioned processes have a possibility of yielding decrypted text that is different from the original plaintext. This phenomenon is called “decryption error”. Here, the patent reference 1, for example, discloses a method of avoiding such decryption errors. In this method, a plaintext is added additional information before being encrypted, and the cipher text is transmitted together with the hash value of the plaintext.
Meanwhile, a mechanism called “key encapsulation mechanism” has recently been proposed as a new notion of the public-key cryptosystem (e.g. refer to the non-patent reference 3). This key encapsulation mechanism is an algorithm that enables distribution of a shared key between a transmission apparatus and a reception apparatus, using the public-key cryptosystem. In this mechanism, the transmission apparatus inputs a public key pk of a receiver into an encryption algorithm E, to generate a cipher text C and a shared key K, and transmits this cipher text C to the reception apparatus. Next, the reception apparatus inputs a secret key sk and the cipher text C into a decryption algorithm D, thereby obtaining the same shared key K that the transmission apparatus owns.
After both of the transmission apparatus and the reception apparatus have established therein the shared key K using the key encapsulation mechanism, as described above, the transmission apparatus encrypts the plaintext to be transmitted to the reception apparatus, according to the symmetric key cryptography and using the shared key K, to generate a cipher text, and transmits the generated cipher text to the reception apparatus. The reception apparatus, in turn, receives the cipher text, and decrypts the received cipher text according to the same symmetric key cryptography and using the shared key K, to generate decrypted text.
With the key encapsulation mechanism, a transmitter cannot take a whole liberty with creation of a shared key, and therefore is prevented from committing fraud even though information is only allowed to be distributed from the transmitter to the receiver. This is the distinctive feature that the conventional arts do not have.
As one example of the mentioned key encapsulation mechanism, an algorithm called PSEC-KEM is disclosed (e.g. the non-patent references 3 and 4). The following describes the PSEC-KEM algorithm disclosed in the non-patent reference 4.
(1) System Parameter of PSEC-KEM
The PSEC-KEM has the following system parameters:                elliptic curve: E        a point with the order of n on the elliptic curve: P        hash functions: G, H        
Note here that the elliptic curve, the order, and the hash functions are detailed in the non-patent reference 1, and so will not be described here.
(2) Public Key and Secret Key of PSEC-KEM                An element x is randomly selected from Zn, to generate W=x*P.        
Here, Zn is a set comprised of {0, 1, . . . , n−1} and x*P signifies a point on the elliptic curve that is obtained by adding up, for x times, the point P on the elliptic curve. Note that the adding method for the point on the elliptic curve is detailed in the non-patent reference 1.                A public key pk is set as (E,P,W,n), and a secret key sk as x.        
(3) Encryption of PSEC-KEM
In encryption, the public key pk is inputted into an encryption algorithm KemE detailed below, thereby outputting a shared key K and a cipher text C. The encryption algorithm KemE is specifically as follows.                Randomly generate an element s whose length is the same as the output length of the hash function H.        Generate G(s), then by dividing G(s), generates a and K. a is a bit sequence comprised of higher order bits of G(s), and K is a bit sequence comprised of the rest of the bits. Here, G(s)=a||K holds. Since “||” is an operand representing a bit connecting, this expression represents that the bit connecting of “a” and “K” yields G(s).        Generate R=a*P, Q=a*W.        Generate v=s xor H(R||Q). Here, “xor” represents bitwise exclusive-or.        Output the shared key K and the cipher text C=(R, v).        
(4) Decryption of PSEC-KEM
In decryption, the cipher text C=(R,v), the public key pk, and the secret key sk are inputted into a decryption algorithm KemD detailed below, thereby outputting a shared key K. The decryption algorithm KemD is specifically as follows.                Generate Q=x*R.        Generate S=v xor H(R||Q)        Generate G(s), and divide G(s) into G(s)=a||K.        See if R=a*P holds. If this holds, the shared key K is outputted.        
When this PSEC-KEM algorithm is applied to the cryptosystem where cryptographic communication is performed between its transmission apparatus and reception apparatus, first of all, the transmission apparatus obtains a public key pk of the reception apparatus which is a communication destination, derives a shared key K and a cipher text C by inputting the obtained public key pk into the aforementioned encryption algorithm KemE, and transmits the cipher text C to the reception apparatus.
Next, the reception apparatus receives the cipher text C from the transmission apparatus, and derives a shared key K by inputting, into the aforementioned decryption algorithm KemD, the cipher text C that is received, and a public key pk and a secret key sk that are owned by the reception apparatus. Here, the shared key K that the reception apparatus has derived is the same as that obtained by the transmission apparatus.
Greater detail is described as follows.
In the PSEC-KEM algorithm, input in the hash function is represented as (a*P||a*W). In the encryption algorithm KemE, v is generated by making the value of H(a*P||a*W) operate on the randomly generated element s.
Meanwhile, in the decryption algorithm KemD, Q=x*R=x*(a*P)=a*(x*P)=a*W is obtained using R=a*P and the secret key sk(=x). From this, it is possible to obtain the random element s from the encryption algorithm KemE, by making the value of H(a*P||a*W) operate on v.
Therefore, in the encryption algorithm KemE and in the decryption algorithm KemD, the same value for s can be inputted in the hash function G, thereby deriving the same shared key K. That is, the reception apparatus owning the secret key sk can derive the shared key K which is the same as that derived by the transmission apparatus.
On the contrary, other reception apparatuses that do not know about the secret key sk(=x) cannot calculate Q=a*W(=(ax)*P) from R=a*P even if they have obtained the public key pk and received the cipher text C. This means that these reception apparatuses cannot derive the same shared key K as that derived by the transmission apparatus.
More specifically, other reception apparatuses that do not know about the secret key sk can only use the public key pk. Therefore in calculation of the aforementioned Q, they have to use W=x*P of the public key pk, instead of the secret key sk(=x). Generally, it is called a Diffie-Hellman problem on an elliptic curve, to try to solve Q=a*W(=(ax)*P) from a*P and W=x*P. This problem is considered impossible to calculate the aforementioned Q without knowing the values for a and x (e.g. refer to the non-patent reference 5).
This means that in the PSEC-KEM algorithm, a shared key K is derived using, in the final stage, the Diffie-Hellman problem with which it is difficult to calculate a*W from a*P without using a secret key. This prevents the shared key K to be derived without knowing the secret key.
As described above, the transmission apparatus and the reception apparatus are enabled to secretly share a shared key K. As a result, data of the communication content is encrypted according to the symmetric key cryptography and using the shared key K, before being transmitted from the transmission apparatus to the reception apparatus using the secret-key cryptography.    (patent reference 1)
Japanese Laid-Open Patent application 2002-252611    (non-patent reference 1)
Tatsuaki Okamoto, Hirosuke Yamamoto “Modern cryptography”, Series/Mathematics in Information Science, Sangyotosho, 1997 (ISBN4-7828-5353-X C3355)    (non-patent reference 2)
Jeffery Hoffstein, Jill Pipher, and Joseph H. Silverman, “NTRU: A ring based public key cryptosystem,” Lecture Notes in Computer Science, 1423, pp. 267-288, Springer-Verlag, 1998.    (non-patent reference 3)
Victor Shoup, “A proposal for an ISO standard for public key encryption (version 2.1)”, online, Dec. 20, 2001 (retrieved on Sep. 29, 2002 on the Internet <URL: http://shoup.net/papers/iso-2—1.pdf>)    (non-patent reference 4)
Tatsuaki Okamoto, “Generic conversions for constructing IND-CCA2 public-key encryption in the random oracle model”, online, The 5th Workshop on Elliptic Curve Cryptography (ECC 2001), Oct. 30, 2001    (non-patent reference 5)
Neal Koblitz, “Algebraic Aspects of Cryptography”, Algorithms and Computation in Mathematics Vol. 3, pp. 132-133, Springer-Verlag, 1998